package com.frx.leetoffer.binarytree;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

/**
 * Created with IDEA
 *
 * @author: xrf
 * @Date: 2019/10/22
 * @Time: 17:56
 */
public class TreeNodeTest {

    private static class TreeNode{
        int val;
        TreeNode left;
        TreeNode right;
        public TreeNode(int val){
            this.val = val;
        }
        public TreeNode(int val,TreeNode left,TreeNode right){
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
    public static void main(String[] args){
       TreeNode treeNode = new TreeNode(1);
       TreeNode treeNode1 = new TreeNode(2);
       TreeNode treeNode2 = new TreeNode(3,treeNode,treeNode1);
       TreeNode treeNode3 = new TreeNode(4);
       TreeNode treeNode4 = new TreeNode(5);
       TreeNode treeNode5 = new TreeNode(6,treeNode3,treeNode4);
       TreeNode treeNode6 = new TreeNode(7,treeNode2,treeNode5);
       preOrder(treeNode6);
       System.out.println();
       midlleOrder(treeNode6);
       System.out.println();
       postOrder(treeNode6);
       System.out.println();
       preIterator(treeNode6);
       System.out.println();
       inIterator(treeNode6);
       System.out.println();
       levelOrder(treeNode6);
    }
    public static void preOrder(TreeNode root){
        if (root == null){
            return;
        }
        System.out.print(root.val + " ");
        preOrder(root.left);
        preOrder(root.right);
    }
    public static void preIterator(TreeNode root){
        if (root == null){
            return;
        }
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()){
            TreeNode cur = stack.pop();
            System.out.print( cur.val + " ");
            if (cur.right != null){
                stack.push(cur.right);
            }
            if (cur.left != null){
                stack.push(cur.left);
            }
        }

    }

    /**
     * @description 二叉树中序遍历的非递归实现 迭代实现
     * @param root
     */
    public static void inIterator(TreeNode root){
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        while (cur != null || !stack.isEmpty()){
            while (cur != null){
                stack.push(cur);
                cur = cur.left;
            }
            cur = stack.pop();
            System.out.print(cur.val + " ");
            cur = cur.right;
        }
    }

    public static void midlleOrder(TreeNode root){
        if (root == null){
            return;
        }
        midlleOrder(root.left);
        System.out.print(root.val + " ");
        midlleOrder(root.right);
    }

    public static void postOrder(TreeNode root){
        if (root == null){
            return;
        }
        postOrder(root.left);
        postOrder(root.right);
        System.out.print(root.val + " ");
    }

    /**
     * 层序遍历 借用队列来实现
     * @param root
     */
    public static void levelOrder(TreeNode root){
        if (root == null){
            return;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()){
            TreeNode cur = queue.remove();
            System.out.print(cur.val + " ");
            if (cur.left != null){
                queue.add(cur.left);
            }
            if (cur.right != null){
                queue.add(cur.right);
            }
        }


    }

}
